package com.likou;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class q994 {

    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int ans = 0;

        int gm = grid.length;
        int gn = grid[0].length;
        List<Integer> m = new ArrayList<>();
        List<Integer> n = new ArrayList<>();
        for (int i = 0; i < gm; i++) {
            for (int j = 0; j < gn; j++) {
                if (grid[i][j] == 2) {
                    m.add(i);
                    n.add(j);
                }
            }
        }

        ans += BFS(grid, m, n);

        // 检测是否还有新鲜的
        for (int[] ints : grid) {
            for (int j = 0; j < gn; j++) {
                if (ints[j] == 1) {
                    return -1;
                }
            }
        }

        return ans;
    }

    public int BFS(int[][] grid, List<Integer> m, List<Integer> n) {
        int gm = grid.length;
        int gn = grid[0].length;

        int ans = 0;

        Queue<List<Integer>> queue = new LinkedList<>();
        for (int i = 0; i < m.size(); i++) {
            queue.offer(List.of(m.get(i), n.get(i)));
        }

        while (!queue.isEmpty()) {
            int size = queue.size();
            int mark = 0;
            for (int i = 0; i < size; i++) {

                List<Integer> poll = queue.poll();
                Integer m1;
                Integer n1;
                // 左边
                m1 = poll.get(0);
                n1 = poll.get(1) - 1;
                if (n1 >= 0 && n1 < gn && grid[m1][n1] == 1) {
                    queue.offer(List.of(m1, n1));
                    grid[m1][n1] = 2;
                    mark = 1;
                }

                // 右边
                m1 = poll.get(0);
                n1 = poll.get(1) + 1;
                if (n1 >= 0 && n1 < gn && grid[m1][n1] == 1) {
                    queue.offer(List.of(m1, n1));
                    grid[m1][n1] = 2;
                    mark = 1;
                }

                // 上面
                m1 = poll.get(0) - 1;
                n1 = poll.get(1);
                if (m1 >= 0 && m1 < gm && grid[m1][n1] == 1) {
                    queue.offer(List.of(m1, n1));
                    grid[m1][n1] = 2;
                    mark = 1;
                }

                // 下面
                m1 = poll.get(0) + 1;
                n1 = poll.get(1);
                if (m1 >= 0 && m1 < gm && grid[m1][n1] == 1) {
                    queue.offer(List.of(m1, n1));
                    grid[m1][n1] = 2;
                    mark = 1;
                }
            }
            if (mark == 1) {
                ans++;
            }
        }

        return ans;
    }

}
